package com.leetcode.根据数据结构分类.数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/2/12
 * @description: 119. 杨辉三角 II
 * https://leetcode-cn.com/problems/pascals-triangle-ii/
 */
public class A_119_杨辉三角II {

    public static void main(String[] args) {
        A_119_杨辉三角II action = new A_119_杨辉三角II();
        List<Integer> res = action.getRow(3);
        System.out.println(res);
    }

    /**
     * 由于 rowIndex 是从 0  开始，所以 len= rowIndex +1
     * 由于只需要求一行的数据，所以可以考虑使用递归
     *
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        int len = rowIndex + 1;
        int[] arr = new int[len];
        getArr(arr, len);

        List<Integer> res = new ArrayList<>(len);
        Arrays.stream(arr).forEach(p -> res.add(p));
        return res;
    }

    private void getArr(int[] arr, int len) {
        if (len == 1) {
            arr[0] = 1;
            return;
        }
        if (len == 2) {
            arr[0] = 1;
            arr[1] = 1;
            return;
        }
        //获取上一个 arr
        getArr(arr, len - 1);
        //逆序就可以避免重复 index 带来的问题
        arr[len - 1] = 1;
        for (int i = len - 2; i > 0; i--) {
            arr[i] += arr[i - 1];
        }
    }
}
